#include "stdafx.h"

#pragma once

template <class DataType>
class Queue
{
	private: 
		struct node 
		{
			DataType data;
			struct node *next;
		};

		struct node *front;
		struct node *rear;

	public: 
		Queue()
		{
			front = NULL;
			rear = NULL;
		}

		bool Enqueue(DataType data)
		{
			struct node *newNode = new struct node;
			
			if(!newNode)
				return (false);

			newNode->data = data;
			newNode->next = NULL;

			// List doesn't exist
			if (!front) 
			{
				front = newNode;
				rear=front;
			}

			// otherwise, at least one node
			rear->next = newNode;
			rear = newNode;

			return (true);
		}

		bool Dequeue(DataType *data)
		{
			struct node *temp = NULL;

			// If Empty, return 
			if(IsEmpty())
			{
				return (false);
			}

			// dequeue front element
			*data = front->data;

			// remove head 
			if (front == rear)
			{
				delete front;
				front = NULL; // just for safety
				rear = NULL;
				return true;
			}
			
			temp = front->next;
			delete front;
			front = temp;
			
			return (true);
		}

		bool IsEmpty()
		{
			return (!front && !rear);
		}
};